class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;


    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
};

public class Solution427 {
    int[][] grid;

    private boolean isLeaf(int startI, int startJ, int endI, int endJ){
        int num = grid[startI][startJ];
        for(int i = startI; i < endI; i++){
            for (int j = startJ; j < endJ; j++) {
                if(num != grid[i][j]){
                    return false;
                }
            }
        }
        return true;
    }

    private Node buildTree(int startI, int startJ, int endI, int endJ){
        if(isLeaf(startI, startJ, endI, endJ)){
            return new Node(grid[startI][startJ] == 1, true);
        }
        Node resNode = new Node(true, false);
        int midI = (startI + endI) / 2, midJ = (startJ + endJ) / 2;
        resNode.topLeft = buildTree(startI, startJ, midI, midJ);
        resNode.topRight = buildTree(startI, midJ, midI, endJ);
        resNode.bottomLeft = buildTree(midI, startJ, endI, midJ);
        resNode.bottomRight = buildTree(midI, midJ, endI, endJ);
        return resNode;
    }

    public Node construct(int[][] grid) {
        this.grid = grid;
        return buildTree(0, 0, grid.length, grid[0].length);
    }
}
